package com.magic.ch07_贪心.乘积最大;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
    static int mod = 1000000009;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        String[] read = br.readLine().split(" ");
        int n = Integer.parseInt(read[0]);
        int k = Integer.parseInt(read[1]);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        Arrays.sort(arr);

        long res = 1;
        int l = 0 ,r = n-1;//双指针
        int sign = 1 ; //正负符号

        if(k%2!=0){
            res=arr[r];
            r--;
            k--;
            if(res < 0){
                sign=-1;
            }
        }
        while(k > 0){
            long x = (long) arr[l]*arr[l+1];
            long y = (long )arr[r]*arr[r-1];
            if(x*sign>y*sign){
                res=x%mod*res%mod;
                l+=2;
            }else{
                res=y%mod*res%mod;
                r-=2;
            }
            k-=2;
        }
        pw.println(res);
        pw.flush();
        pw.close();
    }
}
